\documentclass[scheme=plain]{article}
\usepackage{graphicx} % Required for inserting images
\usepackage{ctex}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{tcolorbox}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=red,urlcolor=grenn]{hyperref}

\lstdefinestyle{cppstyle}{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\color{blue},
  commentstyle=\color{gray}\itshape,
  stringstyle=\color{red},
  numbers=left,
  numberstyle=\tiny\color{gray},
  stepnumber=1,
  numbersep=5pt,
  frame=single,
  breaklines=true,
  breakatwhitespace=false,
  showstringspaces=false,
  tabsize=4
}

\lstdefinestyle{bashstyle}{
    language=bash,                 % 设置语言为 bash
    basicstyle=\ttfamily\small,    % 使用小号等宽字体
    keywordstyle=\color{blue},     % 关键字高亮为蓝色
    commentstyle=\color{green},    % 注释高亮为绿色
    stringstyle=\color{red},       % 字符串高亮为红色
    backgroundcolor=\color{lightgray}, % 背景色
    numbers=left,                  % 在左侧显示行号
    numberstyle=\tiny\color{gray}, % 行号使用小号灰色字体
    stepnumber=1,                  % 行号每一行显示
    numbersep=5pt,                 % 行号与代码的间距
    frame=single,                  % 使用框架
    breaklines=true,               % 自动换行
    showstringspaces=false,        % 不显示字符串中的空格
    tabsize=4,                     % 设置缩进的宽度
    captionpos=b,                  % 标题位置在底部
    literate={~}{$\sim$}{1}        % 处理 ~ 符号
}

\newtcolorbox{asidebox}[2][]
{colback=blue!10!white, colframe=blue!70!black, fonttitle=\bfseries, 
colbacktitle = blue!80!black,title=#2,#1}

\newtcolorbox{definitionbox}[2][]
{colback=green!10!white, colframe=green!70!black, fonttitle=\bfseries, 
colbacktitle = green!80!black,title=#2,#1}

\title{CS:APP Chapter 1 A tour of Computer System}
\author{漢武帝}
\date{July 2025}

\begin{document}

\maketitle

Hello Program in C (hello.c)
\begin{lstlisting}[style=cppstyle]
    #include <stdio.h>
    int main()
    {
        printf("Hello World!\n");
        return 0;
    }
\end{lstlisting}

\section{Information is Bits + Context}
Take the hello.c file as an example. Here, hello.c is called \textbf{source program (or source file)} and is represented by a sequence of ASCII code in a text file. This illustrates a fundamental idea: All information in a system (disk files, programs stored in memory, user data stored in memory, data transferred across a network) is represented as a bunch of bits. The only thing that distinguishes different data objects is the context in which we view them.\\

\begin{definitionbox}{Definition File}
    File = Bits (a sequence of bytes)
\end{definitionbox}

\section{Programs Are Translated by Other Programs into Different Forms}
hello.c is in text form and is readable by a human, but is not executable by a computer. It must be translated to low-level machine-language instructions for execution. Machine language instructions are packaged in a binary file called \textbf{executable object program (executable object file)}.\par

On a Unix system, this process is performed by a \textit{Compiler Driver}:
\begin{figure}
    \centering
    \includegraphics[width=0.9\linewidth]{images/1.png}
    \caption{The compilation system}
    \label{fig:compilation system}
\end{figure}

\section{It Pays to Understand How Compilation Systems Work}
\begin{itemize}
    \item Optimizing program performance
    \item Understanding link-time error
    \item Avoiding security holes
\end{itemize}

\section{Processors Read and Interpret Instructions Stored in Memory}
To compile the source file hello.c on Linux:
\begin{lstlisting}[style=bashstyle]
    linux> gcc -o hello hello.c
\end{lstlisting}
Then run it.
\begin{lstlisting}[style=bashstyle]
    linux> ./hello
    linux> Hello World!
\end{lstlisting}

Both steps are carried out on an application called \textbf{shell}.
\begin{asidebox}{What is shell?}
    The shell is a command-line interpreter that prints a prompt, waits for you
to type a command line, and then performs the command. If the first word of the
command line does not correspond to a built-in shell command, then the shell assumes that it is the name of an executable file that it should load and run.
\end{asidebox}

\subsection{Hardware Organization of a System}
To understand what's under the hood when running programs, we must first understand the hardware organization of the computer. The hardware organization of a system is shown in Figure \ref{fig:Hardware Organization}. The followings definitions are crucial components in the system.\\
\begin{figure}
    \centering
    \includegraphics[width=1\linewidth]{images/2.png}
    \caption{Hardware Organization of a Typical System}
    \label{fig:Hardware Organization}
\end{figure}

\begin{definitionbox}{Buses}
    \begin{itemize}
        \item Buses are electrical conduits that carry bytes of information back and forth between components of a computer.
        \item Typically, buses transfer fixed-size chunks of bytes known as words. The number of bytes in a word is called \textit{word size} (4, 16, 32, 64).
    \end{itemize}
\end{definitionbox}

\begin{definitionbox}{I/O devices}
    I/O devices are the system's connections to the external world. I/O devices are connected to the I/O bus by either a \textit{controller} or \textit{adapter}.
    \begin{itemize}
        \item Contoller: chips sets in the device itself or on the system's main printed board (also called \textit{motherboard}).
        \item Adapter: a card that plugs into a slot on the motherboard.
    \end{itemize}
\end{definitionbox}

\begin{definitionbox}{Main memory}
    Main memory is a temporary storage device that holds both a program and data it manipulates while the processor is executing the program.
    \begin{itemize}
        \item Physically, main memory consists of a collection of \textit{dynamic random access memory} (DRAM) chips.
        \item Logically, memory is organized as a linear array of bytes, each with its own unique address (address index) starting at zero.
        \item In general, each of the machine instructions that constitute a program can consist of a variable number of bytes. The sizes of the data items in C vary according to the types.
    \end{itemize}
\end{definitionbox}

\begin{definitionbox}{CPU}
    The \textit{central processing unit} (CPU or processor) is the engine that interprets (executes) instructions stored in main memory. From the time that power is applied to the system until the time that the power is shut off, a processor repeatedly executes the instruction pointed at by the program counter and updates the program counter to the next instruction. A processor appears to operate according to a very simple instruction execution model, defined by its \textit{instruction set architecture}. 
    \begin{itemize}
        \item Program Counter (PC): a word-size storage device (or register) sits at the core of the CPU, at any point in time, PC points at some machine-language instruction in main memory.
        \item register file: a small storage device that consists of a collection of word-size registers, each with its own unique name.
        \item Arithmetic/Logic Unit (ALU): computes new data and address values.
    \end{itemize}
\end{definitionbox}

A CPU can carry out the following operations at the request of an instruction:
\begin{itemize}
    \item \textit{Load}: Copy a byte or a word from main memory into a register, overwriting the previous contents of the register.
    \item \textit{Store}: Copy a byte or a word from a register into the main memory, overwriting the previous contents of that location.
    \item \textit{Operate}: Copy the contents of two registers to the ALU, perform an arithmetic operation on the two words, and store the result in a register, overwriting the previous contents of that register.
    \item \textit{Jump}: Extract a word from the instruction itself and copy that word into the program counter, overwriting the previous value of the PC.
\end{itemize}

\subsection{Running the hello Program}
A simple version of running hello program. Details are omitted. The whole process is divided into 3 steps:
\begin{enumerate}
    \item Shell program is running and waiting for the user to type command. As typing the ./hello command, shell reads each one into a register and then stores it in memory. As shown in Figure \ref{fig:reading command from keyboard}.
    \item When we hit the enter key at the keyboard, shell knows that we have finished typing, and load the executable hello from disk to memory by executing a sequence of instructions that copies the code and data in the hello object file from the disk, The data contains the string "Hello, World!\textbackslash n". Using a technique called \textit{DMA (Direct Memory Access)}, the data (note not only data but code) travel directly from disk to memory, without passing through the processor as shown in Figure \ref{fig:Loading executable file hello}.
    \item Once the code and data in hello object file are loaded into main memory, the processor begins executing the machine-language instructions in hello program's main routine (main function). These instructions copy "Hello, wolrd!\textbackslash n" from main memory to register file, and from there to display device, where they are displayed on the screen. Shown as Figure \ref{fig:Writing hello world to display device}.
\end{enumerate}

\begin{figure}
    \centering
    \includegraphics[width=0.9\linewidth]{images/3.png}
    \caption{Reading hello command from keyboard}
    \label{fig:reading command from keyboard}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=0.9\linewidth]{images/4.png}
    \caption{Loading hello from disk to main memory}
    \label{fig:Loading executable file hello}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=0.9\linewidth]{images/5.png}
    \caption{Writing the output string from memory to the display.}
    \label{fig:Writing hello world to display device}
\end{figure}

\section{Caches Matter}
To run the hello program, the system need to transfer data between CPU, main memory and I/O devices. We need Caches to make these steps faster. \\
\begin{definitionbox}{Caches}
    Caches are smaller,faster storage devices called cache memories (or simply caches) that serve astemporary staging areas for information that the processor is likely to need in the near future. The L1 and L2 caches are implemented with a hardware technology known as static random access memory (SRAM). See Figure \ref{fig:Cache memories} and Figure \ref{fig:Cache hierarchy}.
\end{definitionbox}

\begin{figure}
    \centering
    \includegraphics[width=0.9\linewidth]{images/6.png}
    \caption{Cache memories}
    \label{fig:Cache memories}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=0.9\linewidth]{images/7.png}
    \caption{Cache hierarchy}
    \label{fig:Cache hierarchy}
\end{figure}

\section{Storage Devices Form a Hierarchy}
See Figure \ref{fig:Cache hierarchy}.

\section{The Operating System Manages the Hardware}
Both the hello and shell programs are not able to access the I/O devices directly, they rely on the services provided by \textit{Operating System}. \\
\begin{asidebox} {Operating System}
    The Operating System can be seen as a layer of software interposed between the application program and the hardware, as shown in Figure \ref{fig:layered view of the system}. That is to say, if you want to manipulate the hardware, you must go through the Operating System.
\end{asidebox}

\begin{figure}
    \centering
    \includegraphics[width=0.9\linewidth]{images/8.png}
    \caption{Operating System interposed between applicaiton program and hardware}
    \label{fig:layered view of the system}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=0.9\linewidth]{images/9.png}
    \caption{Abstractions provided an Operating System}
    \label{fig:Operating System Abstraction}
\end{figure}

As suggested by Figure \ref{fig:Operating System Abstraction}.
\begin{enumerate}
    \item Files are abstractions for I.O devices.
    \item Virtual memory is an abstraction for both the I/O devices and main memory.
    \item Processes are abstractions for the processor, main memory and I/O devices.
\end{enumerate}
 
\subsection{Processes}
\begin{definitionbox}{Process}
    A \textit{process} is the operating system's abstraction for a running program. Multiple processes can run concurrently on the same system, and each process appears to have exclusive use of the hardware. By concurrently, we mean that the instructions of one process are interleaved with the instructions of another process. In most systems, there are more pocesses to run than there are CPUs to run them.
\end{definitionbox}
The Operating System provide the illusion that the program is the only one running on the system by the notion of a process. A single CPU can appear to execute multiple processes concurrently by having the processor switch among them. This interleaving mechanism is called \textit{Context Switching}. 
\begin{definitionbox}{Context}
    The state of each process is called \textit{context}, includes the current values of PC, the register file, and the contents of main memory (note that the main memory is occupied exclusively by the program).
\end{definitionbox}

\begin{figure}
    \centering
    \includegraphics[width=0.9\linewidth]{images/10.png}
    \caption{Process context switching}
    \label{fig:context switching}
\end{figure}

 By context switching, the operating system saves the context of the current process, restroing the context of the new process, and then passing control to the new process. \par
 Figure \ref{fig:context switching} shows context switch between 2 processes. Process A is the shell process, when we ask it to run the hello program, shell invokes a \textit{system call} that passes control to the operating system, the operating system saves the shell's context and creates a new hello process and its context and then passes the control to the new hello process. After the hello process terminates, the operating system passes the control back to the shell process.\\
 \begin{definitionbox}{Kernel}
     The kernel is the portion of the operating system code that is always resident in memory. When an application program requires some action by the operating system, such as to read or write a file, it executes a special system call instruction, transferring control to the kernel. The kernel then performs the requested operation and returns back to the application program. Note that the kernel is not a separate process. Instead, it is a collection of code and data structures that the system uses to manage all the processes.
 \end{definitionbox}

\subsection{Threads}
Mentioned later, not important for now. Each thread is running in the context of the process and sharing the same code and global data.

\subsection{Virtual Memory}
\begin{definitionbox}{Virtual memory}
    \textit{Virtual memory} is an abstration that provides each process with the illusion that it has exclusive use of the main memory. Each process has the same uniform view of memory, which is known as its virtual address space
\end{definitionbox}

\begin{figure}
    \centering
    \includegraphics[width=0.9\linewidth]{images/11.png}
    \caption{Process virtual address space}
    \label{fig:virtual memory}
\end{figure}

As shown in Figure \ref{fig:virtual memory}, the virtual address space has 3 features listed as below:
\begin{enumerate}
    \item The addresses increases from the bottom to the top, 
    \item The lower region of the address space holds the code and the data defined by the user's process.
    \item The topmost region of the address space is reserved for code and data in the operating system and is common to all user's processes.
\end{enumerate}

And these concepts are important:

\begin{itemize}
    \item \textit{Program code and dadta}, Code begins at the same fixed address for all processes, followed by data locations that correspond to global C variables. The code and data areas are initialized directly from the contents of an executable object file.
    \item \textit{Heap}. The code and data areas are followed immediately by the run-time heap. The heap area are not fixed, once up and running, the heap expands and contracts dynamically at run time as a result of calls to C standard library routines such as malloc and free.
    \item \textit{Shared libraries}. Near the middle of the address space are areas for code and data of shared libraries.
    \item \textit{Stack}. At the top of the user's virtual address space is the \textit{user stack} that the compiler uses to implement function calls. Each tiem we call a function, the user stack grows and each time we return from a function, the user stack contracts.
    \item \textit{Kernel virtual memory}. The topmost region of the address space is reserved for the kernel.Application programs are not allowed to read or write the contents of this area or to directly call functions defined in the kernel code. Instead, they must invoke the kernel to perform these operations.
\end{itemize}

\subsection{Files}
Files = A sequence of bytes. 

\section{Systems Communicate with Other Systems Using Networks}
Network can be seen as another I/O device for copying code and data from a system to another. Not important here.

\section{Important Themes}
It turns out that only 9.2 is important.
\subsection{Amdahl’s Law}
\subsection{Concurrency and Parallelism}
\begin{definitionbox}{Concurrency and Parallelism}
    \textit{Concurrency} is the general concept of a system with
multiple, simultaneous activities. \textit{Parammelism} is the use of
concurrency to make a system run faster. Parallelism can be exploited at multiple
levels.
\end{definitionbox}
Uniprocessor system refers to the operating system controls only one CPU. Multiprocessor systems refers to those operating systems that controls more than one CPU (a CPU is also called core under this context). A typical multi-core processor's organization is shown in Figure \ref{fig:multi-core processor}. The chip has four CPU cores, each with its own L1 and L2 caches, and with each L1 cache split into two parts—one to hold recently fetched instructions and one to hold data. The cores share higher levels of cache as well as the interface to main memory.

\subsection{Thread-Level Concurrency}

\begin{definitionbox}{Hyperthrading}
    Hyperthreading, sometimes called simultaneous multi-threading, is a technique
that allows a single CPU to execute multiple flows of control. It involves
having multiple copies of some of the CPU hardware, such as program counters
and register files, while having only single copies of other parts of the hardware, such as the units that perform floating-point arithmetic.
\end{definitionbox}

\begin{figure}
    \centering
    \includegraphics[width=0.9\linewidth]{images/12.png}
    \caption{Multi-core processor organization}
    \label{fig:multi-core processor}
\end{figure}

\subsection{Instruction-Level Parallelism}
An execution of an instruction is divided into different stages and some of these stages can be done in parallel. Processors that can sustain execution rates faster than 1 instruction per cycle are known as superscalar processors.

\subsection{Single-Instruction, Multiple-Data (SIMD) Parallelism}
Just as its name says. These kind of parallelism is suitable for process images, videos and sounds and audios.

\end{document}
